struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#include <climits>

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        // 验证二叉搜索树BST的核心是每个节点的值必须满足
        // 所有左子树节点 < 当前节点 < 所有右子树节点
        // 根节点没有父节点因此没有先天的上下限约束
        // 为了让根节点的第一次范围判断一定通过从而递归验证子树
        // 选择long long类型的极值作为初始范围原因如下
        // 1 int的取值范围是-2147483648到2147483647
        // 2 LLONG_MIN是long long的最小值-9223372036854775808远小于int最小值
        //   LLONG_MAX是long long的最大值9223372036854775807远大于int最大值
        // 3 根节点的值是int类型必然满足LLONG_MIN < 根值 < LLONG_MAX不会误判
        // 4 避免使用int极值导致的边界溢出比如根节点是INT_MAX时右子树无法满足>INT_MAX
        return _isValidBST(root, LLONG_MIN, LLONG_MAX);
    }

    // lower当前节点值必须严格大于的下界由父节点或祖先节点传递而来
    // upper当前节点值必须严格小于的上界由父节点或祖先节点传递而来
    bool _isValidBST(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr)
            return true;
        
        // 核心判断当前节点值是否在合法范围(lower, upper)内
        // 原理根据BST定义当前节点必须大于所有左子树节点因此要大于下界lower
        // 当前节点必须小于所有右子树节点因此要小于上界upper
        // 如果违反这个范围说明当前节点位置不合法直接返回false
        if (root->val >= upper || root->val <= lower)
            return false;
        
        // 递归验证左子树
        // 左子树的所有节点必须小于当前节点的值因此左子树的上界更新为当前节点值root->val
        // 左子树的下界保持不变因为左子树节点还需要满足父节点传递的下界约束
        // 比如祖父节点是10父节点是5左子节点3不仅要<5还要<10下界继承自祖父节点的约束
        bool leftValid = _isValidBST(root->left, lower, root->val);
        
        // 递归验证右子树
        // 右子树的所有节点必须大于当前节点的值因此右子树的下界更新为当前节点值root->val
        // 右子树的上界保持不变因为右子树节点还需要满足父节点传递的上界约束
        // 比如祖父节点是10父节点是15右子节点20不仅要>15还要<10的上界约束不存在这里仅举例
        bool rightValid = _isValidBST(root->right, root->val, upper);
        
        // 结果合并BST要求当前节点合法且左子树合法且右子树合法
        // 只要有一个子树不合法整棵树就不是BST因此用逻辑与&&合并结果
        return leftValid && rightValid;
    }
};